package com.zyk.leetcode;

/**
 * @author zhangsan
 * @date 2021/4/5 17:45
 */
public class J63 {


    // https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof/
    // O(N^)
    // 暴力解
    public static int maxProfit(int[] prices) {
        int ans = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            int max = prices[i];
            for (int j = i; j < prices.length; j++) {
                max = Math.max(max, prices[j]);
            }
            ans = Math.max(ans, (max-prices[i]));
        }
        return ans;
    }

    // 找到股盘最低点, 从那之后看看每天卖的收益记录最小值.
    // O(N)
    public static int maxProfit2(int[] prices) {
        int minprice = Integer.MAX_VALUE;
        int maxprofit = 0;
        for (int price : prices) {
            if (price < minprice) {
                minprice = price;
            } else if (price - minprice > maxprofit) {
                maxprofit = price - minprice;
            }
        }
        return maxprofit;
    }


    // for test
    public static void main(String[] args) {
//        int[] prices = {7,1,5,3,6,4};
        int[] prices = {7,6,4,3,1};
        System.out.println(maxProfit(prices));
        System.out.println(maxProfit2(prices));
    }

}
